package main

import "fmt"

// 如何不使用除法操作负实现两个正整数的除法
// 引申：如何不用加减乘除法运算实现加法、减法、乘法

func main() {
	res, remain := divide1(31, 4)
	fmt.Println("商为", res, " 余数为", remain)

	res, remain = divide2(31, 4)
	fmt.Println("商为", res, " 余数为", remain)

	fmt.Println(add(2, 4))
	fmt.Println(sub(2, 4))
	fmt.Println(mul(2, 4))
	fmt.Println(div(31, 4))
}

// 减法
func divide1(m, n int) (int, int) {
	res := 0

	for m >= n {
		m -= n
		res++
	}

	return res, m
}

// 移位法
func divide2(m, n int) (int, int) {
	res := 0
	var multi int

	for m >= n {
		multi = 1

		for multi*n <= m/2 {
			multi *= 2
		}

		res += multi
		m -= multi * n
	}

	return res, m
}

// 如何不用加减乘除运算实现加法
func add(n1, n2 int) int {
	sum := 0         // 保存不进位相加结果
	carry := -1      // 保存进位值
	for carry != 0 { // 判断进位值是否为 0
		sum = n1 ^ n2
		carry = (n1 & n2) << 1
		n1 = sum
		n2 = carry
	}

	return sum
}

// 如何不用加减乘除运算实现减法
func sub(a, b int) int {
	return add(a, add(^b, 1))
}

// 如何不用加减乘除运算实现乘法
func mul(a, b int) int {
	// 结果的正负数标识
	neg := (a > 0) && (b > 0)

	// 首先计算两个正数相乘的结果，最后根据 neg 确定结果的正负
	if b < 0 {
		b = add(^b, 1)
	}
	if a < 0 {
		a = add(^a, 1)
	}

	result := 0
	bitPosition := make(map[int]int)

	// 计算出 1 向左移位后的值
	for i := 0; i < 32; i++ {
		bitPosition[1<<uint(i)] = i
	}

	for b > 0 {
		// 计算出最后一位 1 的位置编号
		position := bitPosition[b & ^(b-1)]
		result += a << uint(position)
		b &= b - 1 // 去掉最后一位 1
	}

	if !neg {
		result = add(^result, 1)
	}

	return result
}

// 另外一种除法的实现方式
func div(a, b int) int {
	neg := (a > 0) && (b > 0)

	if a < 0 {
		a = add(^a, 1)
	}
	if b < 0 {
		b = add(^b, 1)
	}

	tmpMulti := 0
	result := 1
	for true {
		tmpMulti = mul(b, result)
		if tmpMulti <= a {
			result++
		} else {
			break
		}
	}

	if !neg {
		return add(^(result - 1), 1)
	} else {
		return result - 1
	}
}
